\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}
\sloppy

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 7. Исправления}

\paragraph{Задание 4.} На платцу стоят в одну линию $n$ солдат. Дежурный офицер разбивает эту линию на произвольное число $k$ Непустых отрядов (например, так: первые три солдата, следующие за ними четыре солдата, оставшиеся $n-7>0$ солдат). Затем он в каждом отряде назначает командира. Найти число $h_n$ способов сделать эту операцию.

\begin{Solution}
В этой части я очень поторопился, предположив, что если производящая функция исходной последовательности сдвинута по $x$, то достаточно в производящей функции результата взять коэффициент при соответствующей степени $x$, на самом деле это не так (хотя для обыкновенных производящих функций и очень похоже, но все-таки ошибка).
Итак требуется составить обыкновенную производящую функцию для последовательности:
\[
	0, 1, 2, 3, 4, ...
\]
это количество способов выбрать командира из отряда, очевидно, что когда отряд пустой таких способов нет, когда отряд состоит из $m$ человек, таких способов ровно $m$.

Обыкновенная производящая функция для заданной последовательности:
\[
	\frac{x}{\left(1-x\right)^2}
\]
Производящая функция для результата определяется произведением производящих функций:
\[
	r\left(x\right) = \frac{x^k}{\left(1-x\right)^{2k}}
\]
Разложим производящую функцию:
\[
	\frac{1}{\left(1-x\right)^{2k}} = \sum_{i=0}^{\infty} \left(\binom{2k}{i}\right) x^i
\]
Сделаем домножение на $x^k$, эквивалентный сдвигу:
\[
	\frac{x^k}{\left(1-x\right)^{2k}} = \sum_{i=0}^{\infty} \left(\binom{2k}{i}\right) x^{k+i}
\]
Таким образом количество способов сформировать $k$ из $n$ человек - коэффициет при $x^n$:
\[
	\begin{cases}
		\left(\binom{2k}{n-k}\right) & , k \le n \\
		0 & , k > n
	\end{cases}
\]
\end{Solution}
\paragraph{Задание 5.} Найти ответ в предыдущей задаче в случае, если солдаты не стоят в одну линию. Иными словами, если у офицера имеется возможность выбирать $k$ произвольных неустых подмножеств из $n$-элементного множества солдат.

\begin{Solution}
Задание аналогично предыдущему, но для решения используются экспоненциальные производящие функции, так как изначально солдаты не упорядочены каким-либо построением. Ошибка такая же как и впредыдущей задаче (только здесь она выглядит совсем глупо).

Найдем экспоненциальную производящую функцию для последовательности:
\[
	0, 1, 2, 3, 4, 5 ...
\]
Тут все достаточно просто:
\[
	x e^x
\]
Возводим эту функцию в степень $k$:
\[
	R\left(x\right) = x^k e^{kx}
\]
Разложим $e^{kx}$ в экспоненциальный ряд:
\[
	e^{kx} = \sum_{i=0}^{\infty} k^i \frac{x^i}{i!}
\]
домножаем на $x^k$
\[
	\begin{split}
		& x^ke^{kx} = \sum_{i=0}^{\infty} k^i \frac{x^{i+k}}{i!} = \sum_{i=0}^{\infty} k^i \left(i+k\right)_i \frac{x^{i+k}}{i!\left(i+k\right)_i} = \\
		& = \sum_{i=0}^{\infty} k^i \left(i+k\right)_i \frac{x^{i+k}}{\left(i+k\right)!}
	\end{split}
\]
теперь ответом будет коэффициент при $x^n$:
\[
	\begin{cases}
		k^{n-k} \left(n\right)_{n-k} & , k \le n \\
		0 & , k > n
	\end{cases}
\]
\end{Solution}

\paragraph{Задание 6.} На плацу стоят в одну линию $n$ солдат. Дежурный офицер разбивает эту линию на произвольное число $k$ непустых отрядов (например, так: первые три солдата, следующие четыре, оставшиеся $n-7>0$ солдат). Затем он выбирает некоторое подмножество (возможно, пустое) вновь сформированных отрядов и отправляет их на дежурство. Сколькими способами он может это сделать.

\begin{Solution}
Количество способов разбить строй солдат на $k$ непустых отрядов:
\[
	\frac{x^k}{\left(1-x\right)^k}
\]
где $\frac{x}{1-x}$ - производящая функция для последовательности $0, 1, 1, 1, 1, 1, ...$

Нужное значение стоит перед коэффициентом при $x^n$ в сумме:
\[
	\sum_{i=0}^{\infty} \left(\binom{k}{i}\right) x^{i+k}
\]
т. е.
\[
	\left(\binom{k}{n-k}\right)
\]
Пусть теперь мы сформировали $k$ отрядов, сколькими способоами можно отправить их на дежурство? Для этого необходимо просуммировать выборки по всем $i = \overline{0,k}$ отрядов отправленных на дежурство:
\[
	\sum_{i=0}^{k} \binom{k}{i} \left(\binom{k}{n-k}\right) = \left(\binom{k}{n-k}\right)\left(1+x\right)^k = 2^k \left(\binom{n}{n-k}\right)
\]
\end{Solution}
\end{document}
